Leetcode 1406

basica dp question calc score based on what you can get - what opponent can get.

class Solution {
    Integer[] dp;
    public String stoneGameIII(int[] stoneValue) {
        int n = stoneValue.length;
        dp = new Integer[n + 1];
        int res = helper(stoneValue,0);
        if(res > 0){
            return "Alice";
        }
        if(res < 0){
            return "Bob";
        }
        return "Tie";
    }
    private int helper(int[] stones, int curr){
        // base case 
        if(curr == stones.length) return 0; // no more stone 
        if(dp[curr] != null) return dp[curr]; // solved case

        // our socre is what we have - what opponent can have
        int res = stones[curr] - helper(stones,curr + 1); 
        if(curr + 2 <= stones.length){
            // we can take up to 2 stones
            res = Math.max(res,stones[curr] + stones[curr + 1] - helper(stones,curr + 2));
        }
        if(curr + 3 <= stones.length){
            res = Math.max(res,stones[curr] + stones[curr + 1] + stones[curr + 2] - helper(stones,curr + 3));
        }
        return dp[curr] = res;
    }
}